public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        String[] strs = new String[]{"tars","rats","arts","star"};
        System.out.println(s.numSimilarGroups(strs));
    }

    public int numSimilarGroups(String[] strs) {
        /**
         * 相似字符串组
         *  自己想出来的方法 o(n³)
         *  优化思路：
         *      如何快速判断是否是相似字符串？目前先遍历吧*/
        // 1 预处理
        int n = strs.length;
        int sets = n;
        initialize(n);

        // 2 暴力枚举相似字符串
        for(int i = 0; i < n-1; i++) {
            for(int j = i+1; j < n; j++) {
                // -不在一个集合中时，再进行后续，有效减少无效操作
                if(!isSameSet(i, j)) {
                    // -判断是否相似，相似=>联合，不相似=>不管
                    if(isSimilar(strs[i], strs[j])) {
                        union(i, j);
                        sets --;
                    }
                }
            }
        }

        // 3 返回值
        return sets;
    }

    public static boolean isSimilar(String a, String b) {
        /**
         * 判断两个字符串是否相似*/
        int count = 0;
        for(int i = 0; i < a.length(); i++) {
            if(a.charAt(i) != b.charAt(i)) {
                count ++;
                if(count > 2) {
                    return false;
                }
            }
        }
        return true;
    }

    // 创建并查集
    public static int MAX_N = 300;
    public static int[] father = new int[MAX_N];
    public static int[] size = new int[MAX_N];
    public static int[] stack = new int[MAX_N];

    public static void initialize(int n) {
        /**
         * 对并查集进行初始化*/
        MAX_N = n;
        for(int i = 0; i < n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int a) {
        /**
         * 找到a元素所在集合的代表元素*/
        int i = 0;
        while(a != father[a]) {
            stack[i++] = a;
            a = father[a];
        }
        while(i > 0) {
            father[stack[--i]] = a;
        }
        return a;
    }

    public static boolean isSameSet(int a, int b) {
        /**
         * 判断a、b元素是否在同一集合中*/
        return find(a) == find(b);
    }

    public static void union(int a, int b) {
        /**
         * 合并a、b元素所在集合*/
        // 1 找到a、b元素所在集合代表元素
        int fa = find(a);
        int fb = find(b);

        // 2 小挂大
        if(fa != fb) {
            if(size[fa] >= size[fb]) {
                size[fa] += size[fb];
                father[fb] = fa;
            } else {
                size[fb] += size[fa];
                father[fa] = fb;
            }
        }
    }
}
